2020-05-29 20:16:27

超时解法,迭代次数，4w

class Solution:
    def __init__(self):
        self.count = 0
    
    def rob(self, nums) -> int:
        self.numsLen = len(nums)
        if self.numsLen == 0:
            return 0
        if self.numsLen == 1:
            return nums[0]
        ret = max(self.loop(nums, 0),self.loop(nums, 1))
        return ret
    
    def loop(self, nums, index) -> int:
        if self.numsLen - 2 <= index:
            return nums[index]
            
        if self.numsLen - 3 == index:
            return nums[index] + nums[self.numsLen - 1]

        if self.numsLen - 4 == index:
            return nums[index] + max(nums[self.numsLen - 1], nums[self.numsLen - 2])

        res1 = self.loop(nums, index + 2) + nums[index]
        res2 = self.loop(nums, index + 3) + nums[index]
        return max(res1, res2)

obj = Solution()
inArr = [183,219,57,193,94,233,202,154,65,240,97,234,100,249,186,66,90,238,168,128,177,235,50,81,185,165,217,207,88,80,112,78,135,62,228,247,211]
print(obj.rob(inArr))